package com.zj.leetcode.medium.binarySearch;

/**
 * @program: algorithm
 * @description: 搜索旋转排序数组
 * 33 search-in-rotated-sorted-array
 * @author: Zhang Bo
 * @create: 2022-04-27 14:38:24
 **/
public class SearchInRotatedSortedArray {
    public static void main(String[] args) {
        int[] nums = {4,5,6,7,0,1,2};
        int target = 3;
        Solution solution = new SearchInRotatedSortedArray().new Solution();
        System.out.println(solution.search01(nums, target));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                if (target == nums[i]) {
                    return i;
                }
            }

            return -1;
        }


        public int search01(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            while (l <= r) {
                int mid = (r - l) / 2 + l;
                if(target == nums[mid]){
                    return mid;
                }else {
                    if(target >= nums[r]){
                        r = mid + 1;
                    } else {
                        l = mid - 1;
                    }
                }
            }

            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

